package io.github.maojian.demo;

/**
 * 请勿改变本Java类的包名，类名，方法名，方法参数类型，方法返回值类型
 */

public class AccumulatingWater {

    /**
     * 根据参数计算出积水量，本方法按照竞赛题目要求完成
     *
     * @param heights
     *            给定的柱子高度数组
     * @return 计算出的积水量
     */
    public int compute(int[] heights) {
        int length = heights.length;
        if (length == 0) return 0;

        int[] dpLeft = new int[length];
        dpLeft[0] = heights[0];

        int[] dpRight = new int[length];
        dpRight[length - 1] = heights[length - 1];

        for (int i = 1; i < length; i++) {
            dpLeft[i] = Math.max(dpLeft[i - 1], heights[i]);
        }
        for (int i = length - 2; i >= 0; i--) {
            dpRight[i] = Math.max(dpRight[i + 1], heights[i]);
        }
        int rtn = 0;
        for (int i = 0; i < length; i++) {
            rtn += (Math.min(dpLeft[i], dpRight[i]) - heights[i]);
        }
        return rtn;
    }

    public static void main(String[] args) {
        AccumulatingWater func = new AccumulatingWater();
        int ret = func.compute(new int[]{0, 1, 0, 2, 2, 0, 1, 0, 2});
        System.out.println(ret);
    }
}
